1. Field of the Invention
The present invention relates generally to a software compiler system, and more particularly to a loop scheduler within a software compiler system.
2. Related Art
A compiler includes a loop scheduler to schedule instruction loops for execution. Ideally, a loop scheduler exploits the parallelism between loop iterations to generate tight code that takes advantage of instruction level parallelism.
A conventional loop scheduler is implemented such that it packs a loop into a small number of instructions. The sequence of instructions is called a schedule, and its length is called the iteration interval (II) of the schedule. According to this conventional approach, the loop scheduler schedules code such that one iteration of the loop is performed per execution of the schedule. For a typical loop, the schedule might begin with load instructions, have a middle section composed of arithmetic instructions, and a final section containing store instructions.
This type of schedule has an iteration interval which is at least as great as the length of the longest path through the data precedence graph (DPG) of the loop and only exploits parallelism from within a single iteration of the loop. As will be appreciated, this conventional approach does not make very good use of instruction level parallelism.
Thus, what is required is an improved loop scheduler that exploits the parallelism between loop iterations to generate tight code that takes advantage of instruction level parallelism.